{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Factor Combinations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getFactors"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #因子的组合"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>整数可以被看作是其因子的乘积。</p>\n",
    "\n",
    "<p>例如：</p>\n",
    "\n",
    "<pre>8 = 2 x 2 x 2;\n",
    "  = 2 x 4.</pre>\n",
    "\n",
    "<p>请实现一个函数，该函数接收一个整数 <em>n</em>&nbsp;并返回该整数所有的因子组合。</p>\n",
    "\n",
    "<p><strong>注意：</strong></p>\n",
    "\n",
    "<ol>\n",
    "\t<li>你可以假定 <em>n</em> 为永远为正数。</li>\n",
    "\t<li>因子必须大于 1 并且小于 <em>n</em>。</li>\n",
    "</ol>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入: </strong><code>1</code>\n",
    "<strong>输出: </strong>[]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入: </strong><code>37</code>\n",
    "<strong>输出: </strong>[]</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入: </strong><code>12</code>\n",
    "<strong>输出:</strong>\n",
    "[\n",
    "  [2, 6],\n",
    "  [2, 2, 3],\n",
    "  [3, 4]\n",
    "]</pre>\n",
    "\n",
    "<p><strong>示例 4: </strong></p>\n",
    "\n",
    "<pre><strong>输入: </strong><code>32</code>\n",
    "<strong>输出:</strong>\n",
    "[\n",
    "  [2, 16],\n",
    "  [2, 2, 8],\n",
    "  [2, 2, 2, 4],\n",
    "  [2, 2, 2, 2, 2],\n",
    "  [2, 4, 4],\n",
    "  [4, 8]\n",
    "]\n",
    "</pre>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [factor-combinations](https://leetcode.cn/problems/factor-combinations/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [factor-combinations](https://leetcode.cn/problems/factor-combinations/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['1', '12', '37']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "        return list(self.helper(n, 2))[:-1]\n",
    "    def helper(self, n, start):\n",
    "        d = start\n",
    "        while d * d <= n:\n",
    "            if n % d == 0:\n",
    "                for l in self.helper(n // d, d):\n",
    "                    yield [d] + l\n",
    "            d += 1\n",
    "        yield [n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# ### my:回溯---超时\n",
    "# class Solution:\n",
    "#     def getFactors(self, n: int) -> List[List[int]]:\n",
    "#         self.ans=set()\n",
    "#         def dfs(x,path):\n",
    "#             if x==1:\n",
    "#                 if path:\n",
    "#                     self.ans.add(tuple(sorted(path)))\n",
    "#                 return \n",
    "#             for i in range(2,n):\n",
    "#                 if x%i==0:\n",
    "#                     path.append(i)\n",
    "#                     dfs(x//i,path)\n",
    "#                     path.pop()\n",
    "#         dfs(n,[])\n",
    "#         return [list(p) for p in self.ans]\n",
    "\n",
    "\n",
    "# ###### my:回溯--v2\n",
    "# class Solution:\n",
    "#     def getFactors(self, n: int) -> List[List[int]]:\n",
    "#         self.ans=set()\n",
    "#         @lru_cache(None)\n",
    "#         def dfs(x,path):\n",
    "#             if x==1:\n",
    "#                 if path:\n",
    "#                     self.ans.add(tuple(sorted(path)))\n",
    "#                 return \n",
    "#             for i in range(2,n):\n",
    "#                 if x%i==0:\n",
    "#                     path.append(i)\n",
    "#                     dfs(x//i,path)\n",
    "#                     path.pop()\n",
    "#         dfs(n,[]) ###TypeError: unhashable type: 'list'\n",
    "#         return [list(p) for p in self.ans]\n",
    "\n",
    "# ### 网：回溯\n",
    "# class Solution:\n",
    "#     def getFactors(self,n):\n",
    "\n",
    "#         def dfs(x,start):\n",
    "#             res=[]\n",
    "#             for i in range(start,int(math.sqrt(x))+1):\n",
    "#                 if x%i==0:\n",
    "#                     res.append([i,x//i])\n",
    "##                    #查看n//i能否从因子i开始被拆分成多因子组合\n",
    "#                     for sub in dfs(x//i,i): ### 此处的start为何为i？\n",
    "#                         res.append([i]+sub)\n",
    "#             return res \n",
    "        \n",
    "#         return dfs(n,2)\n",
    "\n",
    "\n",
    "### 火锅bro\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "        def dfs(n,l):\n",
    "            res = []\n",
    "            for i in range(l,int(sqrt(n))+1):\n",
    "                if n % i == 0:\n",
    "                    res.append([i,n//i])\n",
    "                    ###查看n//i能否从因子i开始被拆分成多因子组合\n",
    "                    for sub in dfs(n//i,i):\n",
    "                        res.append(sub+[i])\n",
    "            return res\n",
    "        return dfs(n,2)\n",
    "\n",
    "# 作者：火锅bro哥\n",
    "# 链接：https://leetcode.cn/problems/factor-combinations/\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "        if n == 1:\n",
    "            return []\n",
    "        self.factors = []\n",
    "        i = 2\n",
    "        while i <= n // 2:\n",
    "            if n % i == 0:\n",
    "                self.factors.append(i)\n",
    "            i += 1\n",
    "        self.ans = []\n",
    "        self.backtrace(n, [])\n",
    "        return self.ans\n",
    "\n",
    "    def backtrace(self, curr, lst):\n",
    "        if curr == 1:\n",
    "            self.ans.append(copy.copy(lst))\n",
    "            return\n",
    "        for f in self.factors:\n",
    "            if curr % f == 0:\n",
    "                if lst and f < lst[-1]:\n",
    "                    continue \n",
    "                lst.append(f)\n",
    "                self.backtrace(curr // f, lst)\n",
    "                lst.pop()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "# \tdef getFactors(self, n: int) -> List[List[int]]:\n",
    "\t\t\n",
    "# \t\tdef dfs(start, path, c):\n",
    "# \t\t\tif c < 1:\n",
    "# \t\t\t\treturn\n",
    "# \t\t\tif c == 1:\n",
    "# \t\t\t\tif path:\n",
    "# \t\t\t\t\tres.append(path.copy())\n",
    "# \t\t\t\treturn\n",
    "# \t\t\tfor i in range(start, n):\n",
    "# \t\t\t\tdfs(i, path + [i], c/i)\n",
    "\t\t\t\t\n",
    "# \t\tres = []\n",
    "# \t\tdfs(2, [], n)\n",
    "# \t\treturn res\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\tdef getFactors(self, n: int) -> List[List[int]]:\n",
    "\t\t\n",
    "\t\tdef dfs(start, path, c):\n",
    "\t\t\tif c == 1:\n",
    "\t\t\t\tif path:\n",
    "\t\t\t\t\tres.append(path.copy())\n",
    "\t\t\t\treturn\n",
    "\t\t\tfor i in range(start, n):\n",
    "\t\t\t\tif c % i != 0:\n",
    "\t\t\t\t\tcontinue\n",
    "\t\t\t\tdfs(i, path + [i], c/i)\n",
    "\t\t\t\t\n",
    "\t\tres = []\n",
    "\t\tdfs(2, [], n)\n",
    "\t\treturn res\n",
    "# class Solution:\n",
    "# \tdef getFactors(self, n: int) -> List[List[int]]:\n",
    "# \t\tif n == 1:\n",
    "# \t\t\treturn []\n",
    "# \t\tdef backtrace(start, remain):\n",
    "# \t\t\tfor i in range(start, int(remain**0.5)+1):\n",
    "# \t\t\t\tif remain % i != 0:\n",
    "# \t\t\t\t\tcontinue\n",
    "# \t\t\t\tpath.append(i)\n",
    "# \t\t\t\tres.append(path[:]+[remain // i])\n",
    "# \t\t\t\tbacktrace(i, remain // i)\n",
    "# \t\t\t\tpath.pop()\n",
    "\t\t\t\t\n",
    "# \t\tpath = []\n",
    "# \t\tres = []\n",
    "# \t\tbacktrace(2, n)\n",
    "# \t\treturn res\n",
    "\t\n",
    "\n",
    "# 作者：AccSrd\n",
    "# 链接：https://leetcode.cn/problems/factor-combinations/solutions/1210862/python3-zhao-shang-xia-jie-di-gui-by-acc-hpmr/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n",
    "class Solution:\n",
    "\tdef getFactors(self, n):\n",
    "\t\t\n",
    "\t\tdef DFS(num, start, factors_list, temp):\n",
    "\t\t\tsize = len(temp)\n",
    "\t\t\tif num == 1:\n",
    "\t\t\t\tif size > 1:\n",
    "\t\t\t\t\tfactors_list.append(temp[:])\n",
    "\t\t\telse:\n",
    "\t\t\t\tsqrt = int(num ** 0.5)\n",
    "\t\t\t\tfor i in range(start, sqrt + 1):\n",
    "\t\t\t\t\tif num % i == 0:\n",
    "\t\t\t\t\t\ttemp.append(i)\n",
    "\t\t\t\t\t\tDFS(num // i, i, factors_list, temp)\n",
    "\t\t\t\t\t\ttemp.pop()\n",
    "\t\t\t\ttemp.append(num)\n",
    "\t\t\t\tDFS(1, num, factors_list, temp)\n",
    "\t\t\t\ttemp.pop()\n",
    "\t\t\n",
    "\t\tfactors_list = []\n",
    "\t\ttemp = []\n",
    "\t\tDFS(n, 2, factors_list, temp)\n",
    "\t\treturn factors_list\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "        if n == 1: return []\n",
    "        \n",
    "        def dfs(n, path):\n",
    "            ans = []\n",
    "            \n",
    "            for i in range(path, int(sqrt(n))+1):\n",
    "                if n % i == 0:\n",
    "                    ans.append( [i, n // i] )\n",
    "                    for sub in dfs(n//i, i):\n",
    "                        ans.append(sub + [i])\n",
    "            return ans\n",
    "\n",
    "        return dfs(n, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "        factors_list = []\n",
    "        temp = []\n",
    "        self._get_factors(n, 2, factors_list, temp)\n",
    "        return factors_list\n",
    "\n",
    "    def _get_factors(self, num, start, factors_list, temp):\n",
    "        size = len(temp)\n",
    "        if num == 1:\n",
    "            if size > 1:\n",
    "                factors_list.append(temp.copy())\n",
    "        else:\n",
    "            sqrt = int(num**0.5)\n",
    "            for i in range(start, sqrt+1):\n",
    "                if num % i == 0:\n",
    "                    temp.append(i)\n",
    "                    self._get_factors(num // i, i, factors_list, temp)\n",
    "                    temp.pop()\n",
    "            temp.append(num)\n",
    "            self._get_factors(1, num, factors_list, temp)\n",
    "            temp.pop()\n",
    "            \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "        factorsList = []\n",
    "        temp = []\n",
    "        self.backtrack(n, 2, factorsList, temp)\n",
    "        return factorsList\n",
    "\n",
    "    def backtrack(self, num: int, start: int, factorsList: List[List[int]], temp: List[int]):\n",
    "        if num == 1 and len(temp) > 1:\n",
    "            factorsList.append(temp.copy())\n",
    "            return\n",
    "        for i in range(start, int(num**0.5) + 1):\n",
    "            if num % i == 0:\n",
    "                temp.append(i)\n",
    "                self.backtrack(num // i, i, factorsList, temp)\n",
    "                temp.pop()\n",
    "        if num >= start:\n",
    "            temp.append(num)\n",
    "            self.backtrack(1, num, factorsList, temp)\n",
    "            temp.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# -class Solution:\n",
    "#     def getFactors(self, n: int) -> List[List[int]]:\n",
    "#       res = []\n",
    "#       seq = []\n",
    "\n",
    "#       def helper(i, s):--\n",
    "#         if s == n:\n",
    "#           if len(seq) > 0:\n",
    "#             res.append(copy.copy(seq))\n",
    "#           return s\n",
    "#         if i < 2:\n",
    "#           return s\n",
    "#         if s > n:\n",
    "#           return s\n",
    "#         for j in range(i, 1, -1):\n",
    "#           seq.append(j)\n",
    "#           ans = helper(j, s*j)\n",
    "#           seq.pop()\n",
    "#         return ans\n",
    "      \n",
    "#       ans = helper(n//2, 1)\n",
    "#       return res\n",
    "      \n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "        def dfs(n,l):\n",
    "            res = []\n",
    "            for i in range(l,int(sqrt(n))+1):\n",
    "                if n % i == 0:\n",
    "                    res.append([i,n//i])\n",
    "                    for sub in dfs(n//i,i):\n",
    "                        res.append(sub+[i])\n",
    "            return res\n",
    "        return dfs(n,2)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "        def dfs(n, x):\n",
    "            res = []\n",
    "            for i in range(x, int(sqrt(n)) + 1):\n",
    "                if n % i == 0:\n",
    "                    res.append([i, n // i])\n",
    "                    for sub in dfs(n // i, i):\n",
    "                        res.append(sub + [i])\n",
    "            return res\n",
    "\n",
    "        return dfs(n, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "        def dfs(l,n):\n",
    "            res = []\n",
    "            for i in range(l,int(math.sqrt(n))+1):\n",
    "                if n%i==0:\n",
    "                    res.append([i,n//i])\n",
    "                    for j in dfs(i,n//i):\n",
    "                        res.append([i]+j)\n",
    "            return res\n",
    "        return dfs(2,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        self.dfs(n, 2, [], res)\n",
    "        return res\n",
    "\n",
    "    def dfs(self, n, start, sub_res, res):\n",
    "        if sub_res:\n",
    "            sub_res.append(n)\n",
    "            res.append(sub_res.copy())\n",
    "            sub_res.pop()\n",
    "        \n",
    "        for factor in range(start, int(n ** 0.5) + 1):\n",
    "            if n % factor != 0: continue\n",
    "            sub_res.append(factor)\n",
    "            self.dfs(n // factor, factor, sub_res, res)\n",
    "            sub_res.pop()\n",
    "\n",
    "    #     res = []\n",
    "    #     self.dfs(n, 2, [], res)\n",
    "    #     return res\n",
    "    \n",
    "    # def dfs(self, n, start, sub_res, res):\n",
    "    #     if sub_res:\n",
    "    #         sub_res.append(n)\n",
    "    #         res.append(sub_res.copy())\n",
    "    #         sub_res.pop()\n",
    "\n",
    "    #     for factor in range(start, int(n ** 0.5) + 1):\n",
    "    #         if n % factor != 0: continue\n",
    "    #         sub_res.append(factor)\n",
    "    #         self.dfs(n // factor, factor, sub_res, res)\n",
    "    #         sub_res.pop()\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "        def dfs(num,down):\n",
    "            res=[]\n",
    "            for i in range(down,int(num**0.5)+1):\n",
    "                if num%i==0:\n",
    "                    res.append([i,num//i])\n",
    "                    for sub in dfs(num//i,i):\n",
    "                        res.append(sub+[i])\n",
    "            return res\n",
    "        return dfs(n,2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "\n",
    "        def _dfs(cur_n, l):\n",
    "            result = []\n",
    "\n",
    "            i = l\n",
    "\n",
    "            while i * i <=cur_n:\n",
    "\n",
    "                if  cur_n % i == 0:\n",
    "                    result.append([cur_n //i, i ])\n",
    "\n",
    "                    for sub_list in _dfs(cur_n // i, i):\n",
    "                        sub_list.append(i)\n",
    "                        result.append(sub_list[:])\n",
    "                i += 1\n",
    "            return result\n",
    "\n",
    "        return _dfs(n, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "        def dfs(num,down):\n",
    "            res=[]\n",
    "            for i in range(down,int(num**0.5)+1):\n",
    "                if num%i==0:\n",
    "                    res.append([i,num//i])\n",
    "                    for sub in dfs(num//i,i):\n",
    "                        res.append(sub+[i])\n",
    "            return res\n",
    "        return dfs(n,2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "        def sub_prob(n, start):\n",
    "            if n <= 3:\n",
    "                return []\n",
    "            res = []\n",
    "            for i in range(start, int(n ** 0.5) + 1):\n",
    "                if n % i != 0:\n",
    "                    continue\n",
    "                res.append([i, n // i])\n",
    "                sub_res = sub_prob(n // i, i)\n",
    "                for l in sub_res:\n",
    "                    l.append(i)\n",
    "                    res.append(l)\n",
    "            return res\n",
    "        return sub_prob(n, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "        def dfs(n,l):\n",
    "            res = []\n",
    "            for i in range(l,int(sqrt(n))+1):\n",
    "                if n % i == 0:\n",
    "                    res.append([i,n//i])\n",
    "                    for sub in dfs(n//i,i):\n",
    "                        res.append(sub+[i])\n",
    "            return res\n",
    "        return dfs(n,2)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "        def _get_factors(n, lower_bound):\n",
    "            ans = []\n",
    "\n",
    "            for i in range(lower_bound, isqrt(n) + 1):\n",
    "                if n % i: continue\n",
    "                ans.append([i, n // i])\n",
    "                for factors in _get_factors(n // i, i):\n",
    "                    ans.append([i] + factors)\n",
    "\n",
    "            return ans\n",
    "\n",
    "        return _get_factors(n, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "        def dfs(n, l):\n",
    "            record = []\n",
    "            for i in range(l, int(n**0.5)+1):\n",
    "                if n%i == 0:\n",
    "                    record.append([i, n//i])\n",
    "                    for sub in dfs(n//i, i):\n",
    "                        record.append([i]+sub)\n",
    "            return record\n",
    "\n",
    "        return dfs(n, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "\n",
    "        def dfs(n,l):\n",
    "            res = []\n",
    "            for i in range(l,int(sqrt(n))+1):\n",
    "                if n % i == 0:\n",
    "                    res.append([i,n//i])\n",
    "                    for sub in dfs(n//i,i):\n",
    "                        res.append(sub+[i])\n",
    "            return res\n",
    "        return dfs(n,2)\n",
    "\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "        factors = deque([[n]])\n",
    "        result = []\n",
    "        while factors:\n",
    "            numList = factors.popleft()\n",
    "            num = numList.pop()\n",
    "            if len(numList)>0:\n",
    "                i = numList[len(numList)-1]\n",
    "            else:\n",
    "                i = 2\n",
    "            while i ** 2 <= num:\n",
    "                if num % i == 0:\n",
    "                    mod = num // i\n",
    "                    result.append(numList + [min(mod, i), max(mod, i)])\n",
    "                    factors.append(numList + [min(mod, i), max(mod, i)])\n",
    "                i += 1\n",
    "        \n",
    "        return  result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "        def dfs(n, x):\n",
    "            res = []\n",
    "            for i in range(x, int(math.sqrt(n))+1):\n",
    "                if n % i == 0:\n",
    "                    res.append([i,n//i])\n",
    "                    for tmp in dfs(n//i,i):\n",
    "                        res.append([i]+tmp)\n",
    "            return res\n",
    "        return dfs(n,2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "        factorsList = []\n",
    "        temp = []\n",
    "        self.backtrack(n, 2, factorsList, temp)\n",
    "        return factorsList\n",
    "\n",
    "    def backtrack(self, num: int, start: int, factorsList: List[List[int]], temp: List[int]):\n",
    "        if num == 1 and len(temp) > 1:\n",
    "            factorsList.append(temp.copy())\n",
    "            return\n",
    "        for i in range(start, int(num**0.5) + 1):\n",
    "            if num % i == 0:\n",
    "                temp.append(i)\n",
    "                self.backtrack(num // i, i, factorsList, temp)\n",
    "                temp.pop()\n",
    "        if num >= start:\n",
    "            temp.append(num)\n",
    "            self.backtrack(1, num, factorsList, temp)\n",
    "            temp.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def getFactors(self, n: int) -> List[List[int]]:\n",
    "\n",
    "#         if n==1:\n",
    "#             return []\n",
    "#         res=[]\n",
    "#         def backtrack(n,start,p):\n",
    "#             if n==1:\n",
    "#                 res.append(p)\n",
    "#                 return \n",
    "\n",
    "#             for i in range(start,1,-1):\n",
    "#                 if n%i==0:\n",
    "#                     backtrack(n//i,min(i,n//i),p+[i])\n",
    "        \n",
    "#         backtrack(n,n//2,[])\n",
    "#         return res\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "        def dfs(n,l):\n",
    "            res = []\n",
    "            for i in range(l,int(sqrt(n))+1):\n",
    "                if n % i == 0:\n",
    "                    res.append([i,n//i])\n",
    "                    for sub in dfs(n//i,i):\n",
    "                        res.append(sub+[i])\n",
    "            return res\n",
    "        return dfs(n,2)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "# \tdef getFactors(self, n: int) -> List[List[int]]:\n",
    "\t\t\n",
    "# \t\tdef dfs(start, path, c):\n",
    "# \t\t\tif c < 1:\n",
    "# \t\t\t\treturn\n",
    "# \t\t\tif c == 1:\n",
    "# \t\t\t\tif path:\n",
    "# \t\t\t\t\tres.append(path.copy())\n",
    "# \t\t\t\treturn\n",
    "# \t\t\tfor i in range(start, n):\n",
    "# \t\t\t\tdfs(i, path + [i], c/i)\n",
    "\t\t\t\t\n",
    "# \t\tres = []\n",
    "# \t\tdfs(2, [], n)\n",
    "# \t\treturn res\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\tdef getFactors(self, n: int) -> List[List[int]]:\n",
    "\t\t\n",
    "\t\tdef dfs(start, path, c):\n",
    "\t\t\tif c == 1:\n",
    "\t\t\t\tif path:\n",
    "\t\t\t\t\tres.append(path.copy())\n",
    "\t\t\t\treturn\n",
    "\t\t\tfor i in range(start, n):\n",
    "\t\t\t\tif c % i != 0:\n",
    "\t\t\t\t\tcontinue\n",
    "\t\t\t\tdfs(i, path + [i], c/i)\n",
    "\t\t\t\t\n",
    "\t\tres = []\n",
    "\t\tdfs(2, [], n)\n",
    "\t\treturn res\n",
    "# class Solution:\n",
    "# \tdef getFactors(self, n: int) -> List[List[int]]:\n",
    "# \t\tif n == 1:\n",
    "# \t\t\treturn []\n",
    "# \t\tdef backtrace(start, remain):\n",
    "# \t\t\tfor i in range(start, int(remain**0.5)+1):\n",
    "# \t\t\t\tif remain % i != 0:\n",
    "# \t\t\t\t\tcontinue\n",
    "# \t\t\t\tpath.append(i)\n",
    "# \t\t\t\tres.append(path[:]+[remain // i])\n",
    "# \t\t\t\tbacktrace(i, remain // i)\n",
    "# \t\t\t\tpath.pop()\n",
    "\t\t\t\t\n",
    "# \t\tpath = []\n",
    "# \t\tres = []\n",
    "# \t\tbacktrace(2, n)\n",
    "# \t\treturn res\n",
    "\t\n",
    "\n",
    "# 作者：AccSrd\n",
    "# 链接：https://leetcode.cn/problems/factor-combinations/solutions/1210862/python3-zhao-shang-xia-jie-di-gui-by-acc-hpmr/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n",
    "class Solution:\n",
    "\tdef getFactors(self, n):\n",
    "\t\t\n",
    "\t\tdef DFS(num, start, factors_list, temp):\n",
    "\t\t\tsize = len(temp)\n",
    "\t\t\tif num == 1:\n",
    "\t\t\t\tif size > 1:\n",
    "\t\t\t\t\tfactors_list.append(temp[:])\n",
    "\t\t\telse:\n",
    "\t\t\t\tsqrt = int(num ** 0.5)\n",
    "\t\t\t\tfor i in range(start, sqrt + 1):\n",
    "\t\t\t\t\tif num % i == 0:\n",
    "\t\t\t\t\t\ttemp.append(i)\n",
    "\t\t\t\t\t\tDFS(num // i, i, factors_list, temp)\n",
    "\t\t\t\t\t\ttemp.pop()\n",
    "\t\t\t\ttemp.append(num)\n",
    "\t\t\t\tDFS(1, num, factors_list, temp)\n",
    "\t\t\t\ttemp.pop()\n",
    "\t\t\n",
    "\t\tfactors_list = []\n",
    "\t\ttemp = []\n",
    "\t\tDFS(n, 2, factors_list, temp)\n",
    "\t\treturn factors_list\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "        def dfs(n, x):\n",
    "            res = []\n",
    "            for i in range(x, int(sqrt(n)) + 1):\n",
    "                if n % i == 0:\n",
    "                    res.append([i, n // i])\n",
    "                    for sub in dfs(n // i, i):\n",
    "                        res.append(sub + [i])\n",
    "            return res\n",
    "\n",
    "        return dfs(n, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "        def dfs(i, n):\n",
    "            ret_list = []\n",
    "            for idx in range(i, int(sqrt(n)) + 1):\n",
    "                if n % idx == 0:\n",
    "                    ret_list.append([idx, n // idx])\n",
    "                    temp_list = dfs(idx, n // idx)\n",
    "                    ret_list.extend([[idx] + item for item in temp_list])\n",
    "            return ret_list\n",
    "        \n",
    "        ret = dfs(2, n)\n",
    "        return ret\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# ### my:回溯---超时\n",
    "# class Solution:\n",
    "#     def getFactors(self, n: int) -> List[List[int]]:\n",
    "#         self.ans=set()\n",
    "#         def dfs(x,path):\n",
    "#             if x==1:\n",
    "#                 if path:\n",
    "#                     self.ans.add(tuple(sorted(path)))\n",
    "#                 return \n",
    "#             for i in range(2,n):\n",
    "#                 if x%i==0:\n",
    "#                     path.append(i)\n",
    "#                     dfs(x//i,path)\n",
    "#                     path.pop()\n",
    "#         dfs(n,[])\n",
    "#         return [list(p) for p in self.ans]\n",
    "\n",
    "\n",
    "# ###### my:回溯--v2\n",
    "# class Solution:\n",
    "#     def getFactors(self, n: int) -> List[List[int]]:\n",
    "#         self.ans=set()\n",
    "#         @lru_cache(None)\n",
    "#         def dfs(x,path):\n",
    "#             if x==1:\n",
    "#                 if path:\n",
    "#                     self.ans.add(tuple(sorted(path)))\n",
    "#                 return \n",
    "#             for i in range(2,n):\n",
    "#                 if x%i==0:\n",
    "#                     path.append(i)\n",
    "#                     dfs(x//i,path)\n",
    "#                     path.pop()\n",
    "#         dfs(n,[]) ###TypeError: unhashable type: 'list'\n",
    "#         return [list(p) for p in self.ans]\n",
    "\n",
    "# ### 网：回溯\n",
    "# class Solution:\n",
    "#     def getFactors(self,n):\n",
    "\n",
    "#         def dfs(x,start):\n",
    "#             res=[]\n",
    "#             for i in range(start,int(math.sqrt(x))+1):\n",
    "#                 if x%i==0:\n",
    "#                     res.append([i,x//i])\n",
    "#                     for sub in dfs(x//i,i): ### 此处的start为何为i？\n",
    "#                         res.append([i]+sub)\n",
    "#             return res \n",
    "        \n",
    "#         return dfs(n,2)\n",
    "\n",
    "\n",
    "### 火锅bro\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "        def dfs(n,l):\n",
    "            res = []\n",
    "            for i in range(l,int(sqrt(n))+1):\n",
    "                if n % i == 0:\n",
    "                    res.append([i,n//i])\n",
    "                    for sub in dfs(n//i,i):\n",
    "                        res.append(sub+[i])\n",
    "            return res\n",
    "        return dfs(n,2)\n",
    "\n",
    "# 作者：火锅bro哥\n",
    "# 链接：https://leetcode.cn/problems/factor-combinations/\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "        from math import sqrt, ceil\n",
    "        \n",
    "        if n == 1:\n",
    "            return []\n",
    "\n",
    "        def dfs(n, cur_res, res):\n",
    "            if n == 1:\n",
    "                return \n",
    "            \n",
    "            for i in range(2, int(sqrt(n)) + 1):\n",
    "                if n % i == 0:\n",
    "                    if cur_res and cur_res[-1] > i:\n",
    "                        continue\n",
    "                    \n",
    "                    cur_res.append(i)\n",
    "                    cur_res.append(n // i)\n",
    "\n",
    "                    # sorted_res = sorted(cur_res)\n",
    "                    res.append(list(cur_res))\n",
    "                    \n",
    "                    cur_res.pop()\n",
    "                    \n",
    "                    dfs(n // i, cur_res, res)\n",
    "\n",
    "                    cur_res.pop()\n",
    "\n",
    "        res = []\n",
    "        dfs(n, [], res)\n",
    "        \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "        def dfs(n,l):\n",
    "            res = []\n",
    "            for i in range(l,int(sqrt(n)+1)):\n",
    "                if n%i==0:\n",
    "                    res.append([i, n//i])\n",
    "                    for sub in dfs(n//i,i):\n",
    "                        res.append(sub + [i])\n",
    "            return res\n",
    "        return dfs(n, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.result=[]\n",
    "    def travel(self,n,cur_result):\n",
    "        used=set()\n",
    "        for i in range(2,int(n)):\n",
    "            if len(cur_result)>0 and i<cur_result[-1]:\n",
    "                continue\n",
    "            if i in used:\n",
    "                break\n",
    "            if n%i==0:\n",
    "                cur_result+=[i,n/i]\n",
    "                used.add(i)\n",
    "                used.add(n/i)\n",
    "                if i<=n/i:\n",
    "                    self.result.append(cur_result.copy())\n",
    "                # break\n",
    "                # print(self.result)\n",
    "                cur_result.pop()\n",
    "                self.travel(n/i, cur_result.copy())\n",
    "                cur_result.pop()#回溯\n",
    "    def a(self):\n",
    "        self.result=1\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "        self.travel(n,[])\n",
    "        # self.a()\n",
    "        # print(self.result)\n",
    "        return self.result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "        if n == 1:\n",
    "            return []\n",
    "\n",
    "        # 返回n的最小因子不小于limit的所有因子组合\n",
    "        def fact(n, lo):\n",
    "            result = []\n",
    "            # 此处取sqrt+1便不会出现大于平方根的因子，也就不会重复计算\n",
    "            for f in range(lo, int(n ** 0.5) + 1):\n",
    "                if n % f == 0:\n",
    "                    result.append([f, n // f])\n",
    "                    sub = fact(n // f, f)\n",
    "                    result.extend([[f] + s for s in sub])\n",
    "            return result\n",
    "\n",
    "        return fact(n, 2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "\n",
    "        if n==1:\n",
    "            return []\n",
    "        res=[]\n",
    "        def backtrack(n,start,p):\n",
    "            if n==1:\n",
    "                res.append(p)\n",
    "                return \n",
    "\n",
    "            for i in range(start,1,-1):\n",
    "                if n%i==0:\n",
    "                    backtrack(n//i,min(i,n//i),p+[i])\n",
    "        \n",
    "        backtrack(n,n//2,[])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "\n",
    "        if n==1:\n",
    "            return []\n",
    "\n",
    "        res=[]\n",
    "        def backtrack(n,start,p):\n",
    "            if n==1:\n",
    "                res.append(p)\n",
    "                return \n",
    "\n",
    "            for i in range(start,1,-1):\n",
    "                if n%i==0:\n",
    "                    \n",
    "                    backtrack(n//i,i,p+[i])\n",
    "        \n",
    "        backtrack(n,n-1,[])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "\n",
    "        def DFS(n, cur_ans):\n",
    "            downBound = cur_ans[-1] if cur_ans else 2\n",
    "            upBound = int(n ** 0.5) + 1\n",
    "            if cur_ans: \n",
    "                ans.append(cur_ans + [n])\n",
    "            for factor in range(downBound, upBound):\n",
    "                if n % factor == 0:\n",
    "                    DFS(int(n / factor), cur_ans + [factor])\n",
    "        \n",
    "        ans = []\n",
    "        DFS(n, [])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    \n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "        ans=[]\n",
    "        store=[]\n",
    "\n",
    "        def dfs(val):\n",
    "            start=2\n",
    "            if store:\n",
    "                start=store[-1]\n",
    "            for i in range(start,int(math.sqrt(val))+1):\n",
    "                if val%i==0:\n",
    "                    ans.append(store+[i,val//i])\n",
    "                    store.append(i)\n",
    "                    dfs(val//i)\n",
    "                    store.pop()\n",
    "            \n",
    "        dfs(n)\n",
    "        return ans\n",
    "\n",
    "                    \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "\n",
    "        if n==1:\n",
    "            return []\n",
    "        res=[]\n",
    "        def backtrack(n,start,p):\n",
    "            if n==1:\n",
    "                res.append(p)\n",
    "                return \n",
    "\n",
    "            for i in range(start,1,-1):\n",
    "                if n%i==0:\n",
    "                    backtrack(n//i,min(i,n//i),p+[i])\n",
    "        \n",
    "        backtrack(n,n//2,[])\n",
    "        return res\n",
    "\n",
    "# class Solution:\n",
    "#     def getFactors(self, n: int) -> List[List[int]]:\n",
    "#         def dfs(n,l):\n",
    "#             res = []\n",
    "#             for i in range(l,int(sqrt(n))+1):\n",
    "#                 if n % i == 0:\n",
    "#                     res.append([i,n//i])\n",
    "#                     for sub in dfs(n//i,i):\n",
    "#                         res.append(sub+[i])\n",
    "#             return res\n",
    "#         return dfs(n,2)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# ### my:回溯---超时(无差别前序遍历)\n",
    "# class Solution:\n",
    "#     def getFactors(self, n: int) -> List[List[int]]:\n",
    "#         self.ans=set()\n",
    "#         def dfs(x,path):\n",
    "#             if x==1:\n",
    "#                 if path:\n",
    "#                     self.ans.add(tuple(sorted(path)))\n",
    "#                 return \n",
    "#             for i in range(2,n):\n",
    "#                 if x%i==0:\n",
    "#                     path.append(i)\n",
    "#                     dfs(x//i,path)\n",
    "#                     path.pop()\n",
    "#         dfs(n,[])\n",
    "#         return [list(p) for p in self.ans]\n",
    "\n",
    "\n",
    "# ###### my:回溯--v2\n",
    "# class Solution:\n",
    "#     def getFactors(self, n: int) -> List[List[int]]:\n",
    "#         self.ans=set()\n",
    "#         @lru_cache(None)\n",
    "#         def dfs(x,path):\n",
    "#             if x==1:\n",
    "#                 if path:\n",
    "#                     self.ans.add(tuple(sorted(path)))\n",
    "#                 return \n",
    "#             for i in range(2,n):\n",
    "#                 if x%i==0:\n",
    "#                     path.append(i)\n",
    "#                     dfs(x//i,path)\n",
    "#                     path.pop()\n",
    "#         dfs(n,[]) ###TypeError: unhashable type: 'list'\n",
    "#         return [list(p) for p in self.ans]\n",
    "\n",
    "### 网：由小到大，前序遍历\n",
    "import math\n",
    "class Solution:\n",
    "    def getFactors(self,n):\n",
    "        self.ans=[]\n",
    "\n",
    "        def dfs(x,path,start):\n",
    "            if path: ### 前序添加答案\n",
    "                self.ans.append(path+[x])\n",
    "            for i in range(start,int(math.sqrt(x))+1):\n",
    "                if x%i==0:\n",
    "                    dfs(x//i,path+[i],i)\n",
    "\n",
    "        dfs(n,[],2)\n",
    "        return self.ans\n",
    "\n",
    "\n",
    "# ### 网：回溯\n",
    "# class Solution:\n",
    "#     def getFactors(self,n):\n",
    "\n",
    "#         def dfs(x,start):\n",
    "#             res=[]\n",
    "#             for i in range(start,int(math.sqrt(x))+1):\n",
    "#                 if x%i==0:\n",
    "#                     res.append([i,x//i])\n",
    "##                    #查看n//i能否从因子i开始被拆分成多因子组合\n",
    "#                     for sub in dfs(x//i,i): ### 此处的start为何为i？\n",
    "#                         res.append([i]+sub)\n",
    "#             return res \n",
    "        \n",
    "#         return dfs(n,2)\n",
    "\n",
    "\n",
    "# ### 火锅bro\n",
    "# class Solution:\n",
    "#     def getFactors(self, n: int) -> List[List[int]]:\n",
    "#         def dfs(n,l):\n",
    "#             res = []\n",
    "#             for i in range(l,int(sqrt(n))+1):\n",
    "#                 if n % i == 0:\n",
    "#                     res.append([i,n//i])\n",
    "#                     ###查看n//i能否从因子i开始被拆分成多因子组合\n",
    "#                     for sub in dfs(n//i,i):\n",
    "#                         res.append(sub+[i])\n",
    "#             return res\n",
    "#         return dfs(n,2)\n",
    "\n",
    "# 作者：火锅bro哥\n",
    "# 链接：https://leetcode.cn/problems/factor-combinations/\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def getFactors(self, n: int) -> List[List[int]]:\n",
    "#         def dfs(start,x):\n",
    "#             res=[]\n",
    "#             for i in range(start,int(math.sqrt(x))+1):\n",
    "#                 if x%i==0:\n",
    "#                     res.append([i,x//i])\n",
    "#                     left=dfs(i,x//i) ### error\n",
    "#                     if left:\n",
    "#                         res.append([i]+left[0])\n",
    "#             return res \n",
    "#         return dfs(2,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        path = []\n",
    "        if n == 1:\n",
    "            return res\n",
    "        def dfs(rem, start):            \n",
    "            if rem <= start:\n",
    "                return\n",
    "\n",
    "            for i in range(start, int(pow(rem, 0.5)+1)):\n",
    "                if rem % i == 0:\n",
    "                    path.append(i)\n",
    "                    res.append(path[:] + [rem//i])\n",
    "                    dfs(rem//i, i)\n",
    "                    path.pop()\n",
    "        \n",
    "        dfs(n,2)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        cur = []\n",
    "        def dfs(num ,l):\n",
    "            if cur:\n",
    "                res.append(cur[:] + [num])\n",
    "            for i in range(l, int(pow(num, 0.5))+1):\n",
    "                if num % i == 0:\n",
    "                    cur.append(i)\n",
    "                    dfs(num // i, i)\n",
    "                    cur.pop()\n",
    "        dfs(n,2)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "        paths = []\n",
    "        cur = []\n",
    "        self.out = 1\n",
    "        nums = [i for i in range(2,n//2+1) if n%i==0]\n",
    "        def dfs(i):\n",
    "            if self.out>1 and self.out == n:\n",
    "                paths.append(cur[:])\n",
    "            for j in range(i,len(nums)):\n",
    "                if n%(self.out*nums[j])==0:\n",
    "                    self.out*=nums[j]\n",
    "                    cur.append(nums[j])\n",
    "                    dfs(j)\n",
    "                    self.out/=nums[j]\n",
    "                    cur.pop()\n",
    "        dfs(0)\n",
    "        return paths\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        def dfs(k, n, path):\n",
    "            for i in range(k, int(n**0.5)+1):\n",
    "                if n%i == 0:\n",
    "                    answer = path+[i]+[n//i]\n",
    "                    ans.append(answer)\n",
    "                    dfs(i, n//i, path+[i])\n",
    "        if n <= 3:\n",
    "            return []\n",
    "        dfs(2, n, [])\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        arr = []\n",
    "        for i in range(2, n):\n",
    "            if n % i == 0:\n",
    "                arr.append(i) \n",
    "        m = len(arr) \n",
    "        def dfs(n, vec, i):\n",
    "            if n == 1:\n",
    "                if len(vec) > 1:\n",
    "                    ans.append(copy.deepcopy(vec)) \n",
    "            for j in range(i, m):\n",
    "                if n < arr[j]:\n",
    "                    break \n",
    "                if n % arr[j] == 0:\n",
    "                    dfs(n//arr[j], vec + [arr[j]], j)\n",
    "        dfs(n, [], 0) \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "\n",
    "        if n==1:\n",
    "            return []\n",
    "\n",
    "        res=[]\n",
    "        def backtrack(n,start,p):\n",
    "            if n==1:\n",
    "                res.append(p)\n",
    "                return \n",
    "\n",
    "            for i in range(start,1,-1):\n",
    "                if n%i==0:\n",
    "                    backtrack(n//i,min(i,n//i),p+[i])\n",
    "        \n",
    "        backtrack(n,n-1,[])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        cur = []\n",
    "        def dfs(num, l):\n",
    "            if cur:\n",
    "                res.append(cur[:] + [num])\n",
    "            for i in range(l, int(pow(num, 0.5)) + 1):\n",
    "                if num % i == 0:\n",
    "                    cur.append(i)\n",
    "                    dfs(num // i, i)\n",
    "                    cur.pop()\n",
    "        dfs(n, 2)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "# \tdef getFactors(self, n: int) -> List[List[int]]:\n",
    "\t\t\n",
    "# \t\tdef dfs(start, path, c):\n",
    "# \t\t\tif c < 1:\n",
    "# \t\t\t\treturn\n",
    "# \t\t\tif c == 1:\n",
    "# \t\t\t\tif path:\n",
    "# \t\t\t\t\tres.append(path.copy())\n",
    "# \t\t\t\treturn\n",
    "# \t\t\tfor i in range(start, n):\n",
    "# \t\t\t\tdfs(i, path + [i], c/i)\n",
    "\t\t\t\t\n",
    "# \t\tres = []\n",
    "# \t\tdfs(2, [], n)\n",
    "# \t\treturn res\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\tdef getFactors(self, n: int) -> List[List[int]]:\n",
    "\t\t\n",
    "\t\tdef dfs(start, path, c):\n",
    "\t\t\tif c == 1:\n",
    "\t\t\t\tif path:\n",
    "\t\t\t\t\tres.append(path.copy())\n",
    "\t\t\t\treturn\n",
    "\t\t\tfor i in range(start, n):\n",
    "\t\t\t\tif c % i != 0:\n",
    "\t\t\t\t\tcontinue\n",
    "\t\t\t\tdfs(i, path + [i], c/i)\n",
    "\t\t\t\t\n",
    "\t\tres = []\n",
    "\t\tdfs(2, [], n)\n",
    "\t\treturn res\n",
    "# class Solution:\n",
    "# \tdef getFactors(self, n: int) -> List[List[int]]:\n",
    "# \t\tif n == 1:\n",
    "# \t\t\treturn []\n",
    "# \t\tdef backtrace(start, remain):\n",
    "# \t\t\tfor i in range(start, int(remain**0.5)+1):\n",
    "# \t\t\t\tif remain % i != 0:\n",
    "# \t\t\t\t\tcontinue\n",
    "# \t\t\t\tpath.append(i)\n",
    "# \t\t\t\tres.append(path[:]+[remain // i])\n",
    "# \t\t\t\tbacktrace(i, remain // i)\n",
    "# \t\t\t\tpath.pop()\n",
    "\t\t\t\t\n",
    "# \t\tpath = []\n",
    "# \t\tres = []\n",
    "# \t\tbacktrace(2, n)\n",
    "# \t\treturn res\n",
    "\t\n",
    "\n",
    "# 作者：AccSrd\n",
    "# 链接：https://leetcode.cn/problems/factor-combinations/solutions/1210862/python3-zhao-shang-xia-jie-di-gui-by-acc-hpmr/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n",
    "class Solution:\n",
    "\tdef getFactors(self, n):\n",
    "\t\t\n",
    "\t\tdef DFS(remain, start, path):\n",
    "\t\t\tsize = len(path)\n",
    "\t\t\tif remain == 1:\n",
    "\t\t\t\tif size > 1:\n",
    "\t\t\t\t\tres.append(path[:])\n",
    "\t\t\telse:\n",
    "\t\t\t\tfor i in range(start, int(remain ** 0.5) + 1):\n",
    "\t\t\t\t\tif remain % i == 0:\n",
    "\t\t\t\t\t\tDFS(remain // i, i, path + [i])\n",
    "\t\t\t\tpath.append(remain)\n",
    "\t\t\t\tDFS(1, remain, path)\n",
    "\t\t\t\tpath.pop()\n",
    "\t\t\t\t\n",
    "\t\tres = []\n",
    "\t\tpath = []\n",
    "\t\tDFS(n, 2, path)\n",
    "\t\treturn res\t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "        ans,path=[],[]\n",
    "        def back(num,l):\n",
    "            if num==1:\n",
    "                return\n",
    "            for i in range(l,int(num**0.5)+1):\n",
    "                if num%i==0:\n",
    "                    path.append(i)\n",
    "                    new=path+[num//i]\n",
    "                    ans.append(new.copy())\n",
    "                    back(num//i,i)\n",
    "                    path.pop()\n",
    "        back(n,2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "        def dfs(n, cur_ans):\n",
    "            # 确定每次取值的上界以及下界，避免重复取值\n",
    "            down_bound = cur_ans[-1] if cur_ans else 2\n",
    "            up_bound = int(pow(n, 0.5)) + 1\n",
    "\n",
    "            if cur_ans:  # 每次递归都会获得一个组合\n",
    "                ans.append(cur_ans + [n])  # 合并数组添加到ans中\n",
    "            for factor in range(down_bound, up_bound):\n",
    "                if n % factor == 0:\n",
    "                    dfs(n/factor, cur_ans + [factor])\n",
    "            \n",
    "        ans = []\n",
    "        dfs(n, [])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "# \tdef getFactors(self, n: int) -> List[List[int]]:\n",
    "\t\t\n",
    "# \t\tdef dfs(start, path, c):\n",
    "# \t\t\tif c < 1:\n",
    "# \t\t\t\treturn\n",
    "# \t\t\tif c == 1:\n",
    "# \t\t\t\tif path:\n",
    "# \t\t\t\t\tres.append(path.copy())\n",
    "# \t\t\t\treturn\n",
    "# \t\t\tfor i in range(start, n):\n",
    "# \t\t\t\tdfs(i, path + [i], c/i)\n",
    "\t\t\t\t\n",
    "# \t\tres = []\n",
    "# \t\tdfs(2, [], n)\n",
    "# \t\treturn res\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "        import math\n",
    "        if n == 1:\n",
    "            return []\n",
    "        def backtrace(m, start):\n",
    "            for i in range(start, int(math.sqrt(m)+1)):\n",
    "                if m % i != 0:\n",
    "                    continue\n",
    "                path.append(i)\n",
    "                res.append(path[:]+[m // i])\n",
    "                backtrace(m // i, i)\n",
    "                path.pop()\n",
    "\n",
    "        path = []\n",
    "        res = []\n",
    "        backtrace(n, 2)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "# 作者：AccSrd\n",
    "# 链接：https://leetcode.cn/problems/factor-combinations/solutions/1210862/python3-zhao-shang-xia-jie-di-gui-by-acc-hpmr/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "        s= str(n)\n",
    "        ans = []\n",
    "        def dfs(n, vec, i):\n",
    "            if n== 1:\n",
    "                if len(vec) > 1:\n",
    "                    ans.append(copy.deepcopy(vec)) \n",
    "                return \n",
    "            for j in range(i, int(math.sqrt(n)) + 1):\n",
    "                if n % j == 0:\n",
    "                    dfs(n//j, vec + [j], j) \n",
    "            dfs(1, vec + [n], n)\n",
    "        dfs(n, [], 2)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "        cur = []\n",
    "        res = []\n",
    "        def dfs(num, low):\n",
    "            if cur:\n",
    "                res.append(cur + [num])\n",
    "            for i in range(low, int(sqrt(num)) + 1):\n",
    "                if num % i == 0:\n",
    "                    cur.append(i)\n",
    "                    dfs(num // i, i)\n",
    "                    cur.pop()\n",
    "        dfs(n, 2)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "\n",
    "        ans = []\n",
    "        def dfs(n, path):\n",
    "            if len(path) > 0:\n",
    "                if n == 1:\n",
    "                    ans.append(path[:])\n",
    "                    return \n",
    "                if n < path[-1]:\n",
    "                    return \n",
    "                prev = path[-1]\n",
    "                for i in range(prev, n+1):\n",
    "                    if i * i > n:\n",
    "                        break\n",
    "                    if n % i == 0:\n",
    "                        path.append(i)\n",
    "                        dfs(n // i, path)\n",
    "                        path.pop()\n",
    "                path.append(n)\n",
    "                dfs(1, path)\n",
    "                path.pop()\n",
    "                return \n",
    "            else:\n",
    "                for i in range(2, n):\n",
    "                    if i * i > n:\n",
    "                        break\n",
    "                    if n % i == 0:\n",
    "                        path.append(i)\n",
    "                        dfs(n // i, path)\n",
    "                        path.pop()\n",
    "                return \n",
    "        dfs(n, [])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        path = []\n",
    "        def backtrace(n: int,factor: int) -> None:\n",
    "            nonlocal res, path\n",
    "            for i in range(factor, isqrt(n)+1):\n",
    "                if n%i: continue\n",
    "                path.append(i)\n",
    "\n",
    "                path.append(n//i)\n",
    "                res.append(copy.deepcopy(path))\n",
    "                path.pop()\n",
    "\n",
    "                backtrace(n//i, i)\n",
    "\n",
    "                path.pop()\n",
    "\n",
    "        backtrace(n, 2)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "\n",
    "        if n==1:\n",
    "            return []\n",
    "\n",
    "        res=[]\n",
    "        def backtrack(n,start,p):\n",
    "            if n==1:\n",
    "                res.append(p)\n",
    "                return \n",
    "\n",
    "            for i in range(start,1,-1):\n",
    "                if n%i==0:\n",
    "                    print(i,n)\n",
    "                    backtrack(n//i,min(i,n//i),p+[i])\n",
    "        \n",
    "        backtrack(n,n-1,[])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        def backtrace(curNum, curRes):\n",
    "            nonlocal res\n",
    "            if curRes:\n",
    "                tmp = curRes.copy()\n",
    "                tmp.append(curNum)\n",
    "                res.append(tmp)\n",
    "            if curNum == 1:\n",
    "                return\n",
    "            \n",
    "            for i in range(2, int(curNum // 2)+1):\n",
    "                if not curNum % i:\n",
    "                    if int(curNum//i) < i or (curRes and i < curRes[-1]):\n",
    "                        # print(curRes, i, curNum//i)\n",
    "                        continue\n",
    "                    curRes.append(i)\n",
    "                    backtrace(int(curNum//i), curRes)\n",
    "                    curRes.pop(-1)\n",
    "        backtrace(n,[])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "        \n",
    "        def dfs(n, nums):\n",
    "            top_line = int(pow(n, 0.5)) + 1\n",
    "            down_line = nums[-1] if nums else 2\n",
    "\n",
    "            if nums:\n",
    "                res.append(nums + [n])\n",
    "            for i in range(down_line, top_line):\n",
    "                if n % i == 0:\n",
    "                    dfs(int(n/i), nums + [i])\n",
    "\n",
    "        res = []\n",
    "        dfs(n, [])\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "        \n",
    "        res = []\n",
    "        def dfs(s,stack):\n",
    "            if stack and s >= stack[-1]:\n",
    "                res.append(stack[:]+[s])\n",
    "            #print(s,stack)\n",
    "            for x in range(2 if not stack else stack[-1],s//2+1):\n",
    "                if s % x == 0:\n",
    "                    dfs(s//x,stack+[x])\n",
    "        dfs(n,[])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "        ans=[]\n",
    "        temp=[]\n",
    "        def dfs(n,f):\n",
    "            for i in range(f,int(n**0.5+1)):\n",
    "                if n%i==0:\n",
    "                    temp.append(i)\n",
    "                    temp.append(n//i)\n",
    "                    ans.append(temp[:])\n",
    "                    temp.pop()\n",
    "                    dfs(n//i,i)\n",
    "                    temp.pop()\n",
    "        dfs(n,2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "        ans,path=[],[]\n",
    "        def back(num,l):\n",
    "            if num==1:\n",
    "                return\n",
    "            for i in range(l,int(num**0.5)+1):\n",
    "                if num%i==0:\n",
    "                    path.append(i)\n",
    "                    new=path+[num//i]\n",
    "                    ans.append(new.copy())\n",
    "                    back(num//i,i)\n",
    "                    path.pop()\n",
    "        back(n,2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "# \tdef getFactors(self, n: int) -> List[List[int]]:\n",
    "\t\t\n",
    "# \t\tdef dfs(start, path, c):\n",
    "# \t\t\tif c < 1:\n",
    "# \t\t\t\treturn\n",
    "# \t\t\tif c == 1:\n",
    "# \t\t\t\tif path:\n",
    "# \t\t\t\t\tres.append(path.copy())\n",
    "# \t\t\t\treturn\n",
    "# \t\t\tfor i in range(start, n):\n",
    "# \t\t\t\tdfs(i, path + [i], c/i)\n",
    "\t\t\t\t\n",
    "# \t\tres = []\n",
    "# \t\tdfs(2, [], n)\n",
    "# \t\treturn res\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "        import math\n",
    "        if n == 1:\n",
    "            return []\n",
    "        def backtrace(m, start):\n",
    "            for i in range(start, int(math.sqrt(m)+1)):\n",
    "                if m % i != 0:\n",
    "                    continue\n",
    "                path.append(i)\n",
    "                res.append(path[:]+[m // i])\n",
    "                backtrace(m // i, i)\n",
    "                path.pop()\n",
    "\n",
    "        path = []\n",
    "        res = []\n",
    "        backtrace(n, 2)\n",
    "        return res\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "# \tdef getFactors(self, n: int) -> List[List[int]]:\n",
    "\t\t\n",
    "# \t\tdef dfs(start, path, c):\n",
    "# \t\t\tif c == 1:\n",
    "# \t\t\t\tif path:\n",
    "# \t\t\t\t\tres.append(path.copy())\n",
    "# \t\t\t\treturn\n",
    "# \t\t\tfor i in range(start, n):\n",
    "# \t\t\t\tif c % i != 0:\n",
    "# \t\t\t\t\tcontinue\n",
    "# \t\t\t\tdfs(i, path + [i], c/i)\n",
    "\t\t\t\t\n",
    "# \t\tres = []\n",
    "# \t\tdfs(2, [], n)\n",
    "# \t\treturn res\n",
    "\n",
    "# 作者：AccSrd\n",
    "# 链接：https://leetcode.cn/problems/factor-combinations/solutions/1210862/python3-zhao-shang-xia-jie-di-gui-by-acc-hpmr/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "        if n == 1: return []\n",
    "        result = []\n",
    "        solution = []\n",
    "        def traverse(x: int, aim: int):\n",
    "            for i in range(x, int(math.sqrt(aim))+1):\n",
    "                remain = aim % i\n",
    "                if remain == 0:\n",
    "                    solution.append(i)\n",
    "                    result.append(solution[:]+[aim//i])\n",
    "                    traverse(i, aim//i)\n",
    "                    solution.pop()\n",
    "                            \n",
    "        traverse(2, n)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "\n",
    "        def dfs(i, n, vec):\n",
    "            if n == 1:\n",
    "                if len(vec) > 1:\n",
    "                    ans.append(vec)\n",
    "                return \n",
    "            for j in range(i, int(math.sqrt(n))+1):\n",
    "                if n % j == 0:\n",
    "                    dfs(j, n//j, vec+[j])\n",
    "            dfs(n,1, vec+[n]) \n",
    "        ans = []\n",
    "        dfs(2, n, [])\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "# \tdef getFactors(self, n: int) -> List[List[int]]:\n",
    "\t\t\n",
    "# \t\tdef dfs(start, path, c):\n",
    "# \t\t\tif c < 1:\n",
    "# \t\t\t\treturn\n",
    "# \t\t\tif c == 1:\n",
    "# \t\t\t\tif path:\n",
    "# \t\t\t\t\tres.append(path.copy())\n",
    "# \t\t\t\treturn\n",
    "# \t\t\tfor i in range(start, n):\n",
    "# \t\t\t\tdfs(i, path + [i], c/i)\n",
    "\t\t\t\t\n",
    "# \t\tres = []\n",
    "# \t\tdfs(2, [], n)\n",
    "# \t\treturn res\n",
    "\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "# \tdef getFactors(self, n: int) -> List[List[int]]:\n",
    "\t\t\n",
    "# \t\tdef dfs(start, path, c):\n",
    "# \t\t\tif c == 1:\n",
    "# \t\t\t\tif path:\n",
    "# \t\t\t\t\tres.append(path.copy())\n",
    "# \t\t\t\treturn\n",
    "# \t\t\tfor i in range(start, n):\n",
    "# \t\t\t\tif c % i != 0:\n",
    "# \t\t\t\t\tcontinue\n",
    "# \t\t\t\tdfs(i, path + [i], c/i)\n",
    "\t\t\t\t\n",
    "# \t\tres = []\n",
    "# \t\tdfs(2, [], n)\n",
    "# \t\treturn res\n",
    "\n",
    "class Solution:\n",
    "\tdef getFactors(self, n: int) -> List[List[int]]:\n",
    "\t\tif n == 1:\n",
    "\t\t\treturn []\n",
    "\t\tdef backtrace(m, start):\n",
    "\t\t\tfor i in range(start, int(m**0.5)+1):\n",
    "\t\t\t\tif m % i != 0:\n",
    "\t\t\t\t\tcontinue\n",
    "\t\t\t\tpath.append(i)\n",
    "\t\t\t\tres.append(path[:]+[m // i])\n",
    "\t\t\t\tbacktrace(m // i, i)\n",
    "\t\t\t\tpath.pop()\n",
    "\t\t\t\t\n",
    "\t\tpath = []\n",
    "\t\tres = []\n",
    "\t\tbacktrace(n, 2)\n",
    "\t\treturn res\n",
    "        \n",
    "# 作者：AccSrd\n",
    "# 链接：https://leetcode.cn/problems/factor-combinations/solutions/1210862/python3-zhao-shang-xia-jie-di-gui-by-acc-hpmr/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "# \tdef getFactors(self, n: int) -> List[List[int]]:\n",
    "\t\t\n",
    "# \t\tdef dfs(start, path, c):\n",
    "# \t\t\tif c < 1:\n",
    "# \t\t\t\treturn\n",
    "# \t\t\tif c == 1:\n",
    "# \t\t\t\tif path:\n",
    "# \t\t\t\t\tres.append(path.copy())\n",
    "# \t\t\t\treturn\n",
    "# \t\t\tfor i in range(start, n):\n",
    "# \t\t\t\tdfs(i, path + [i], c/i)\n",
    "\t\t\t\t\n",
    "# \t\tres = []\n",
    "# \t\tdfs(2, [], n)\n",
    "# \t\treturn res\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "        import math\n",
    "        if n == 1:\n",
    "            return []\n",
    "        def backtrace(m, start):\n",
    "            for i in range(start, int(math.sqrt(m)+1)):\n",
    "                if m % i != 0:\n",
    "                    continue\n",
    "                path.append(i)\n",
    "                res.append(path[:]+[m // i])\n",
    "                backtrace(m // i, i)\n",
    "                path.pop()\n",
    "\n",
    "        path = []\n",
    "        res = []\n",
    "        backtrace(n, 2)\n",
    "        return res\n",
    "\n",
    "\n",
    "# 作者：AccSrd\n",
    "# 链接：https://leetcode.cn/problems/factor-combinations/solutions/1210862/python3-zhao-shang-xia-jie-di-gui-by-acc-hpmr/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        now = []\n",
    "        def dfs(l, nownum):\n",
    "            if now:\n",
    "                ans.append(copy.deepcopy(now) + [nownum])\n",
    "            for i in range(l, int(nownum ** 0.5) + 1):\n",
    "                if nownum % i == 0:\n",
    "                    now.append(i)\n",
    "                    dfs(i, nownum // i)\n",
    "                    now.pop()\n",
    "        dfs(2, n)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "        ans=[]\n",
    "        def dfs(i,tmp,arr):\n",
    "            nonlocal ans\n",
    "            if arr!=[]:\n",
    "                ans.append(arr[:]+[tmp])\n",
    "            for j in range(i, int(pow(tmp, 0.5))+1):\n",
    "                if tmp%j==0 :\n",
    "                    arr1=arr.copy()\n",
    "                    arr1=arr1+[j]\n",
    "                    dfs(j,tmp//j,arr1)\n",
    "\n",
    "            return \n",
    "\n",
    "\n",
    "        dfs(2,n,[])\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "# \tdef getFactors(self, n: int) -> List[List[int]]:\n",
    "\t\t\n",
    "# \t\tdef dfs(start, path, c):\n",
    "# \t\t\tif c < 1:\n",
    "# \t\t\t\treturn\n",
    "# \t\t\tif c == 1:\n",
    "# \t\t\t\tif path:\n",
    "# \t\t\t\t\tres.append(path.copy())\n",
    "# \t\t\t\treturn\n",
    "# \t\t\tfor i in range(start, n):\n",
    "# \t\t\t\tdfs(i, path + [i], c/i)\n",
    "\t\t\t\t\n",
    "# \t\tres = []\n",
    "# \t\tdfs(2, [], n)\n",
    "# \t\treturn res\n",
    "\n",
    "class Solution:\n",
    "\tdef getFactors(self, n: int) -> List[List[int]]:\n",
    "\t\t\n",
    "\t\tdef dfs(start, path, c):\n",
    "\t\t\tif c > n:\n",
    "\t\t\t\treturn\n",
    "\t\t\tif c == n:\n",
    "\t\t\t\tif path:\n",
    "\t\t\t\t\tres.append(path.copy())\n",
    "\t\t\t\treturn\n",
    "\t\t\tfor i in range(start, int(n ** 0.5) + 1):\n",
    "\t\t\t\tif i * c > n:\n",
    "\t\t\t\t\treturn\n",
    "\t\t\t\tdfs(i, path + [i], c * i)\n",
    "\t\t\t\t\n",
    "\t\tres = []\n",
    "\t\tdfs(2, [], 1)\n",
    "\t\treturn res\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "\n",
    "        def DFS(n, cur_ans):\n",
    "            downBound = cur_ans[-1] if cur_ans else 2\n",
    "            upBound = int(n ** 0.5) + 1\n",
    "            if cur_ans: \n",
    "                ans.append(cur_ans + [n])\n",
    "            for factor in range(downBound, upBound):\n",
    "                if n % factor == 0:\n",
    "                    DFS(int(n / factor), cur_ans + [factor])\n",
    "        \n",
    "        ans = []\n",
    "        DFS(n, [])\n",
    "        return ans\n",
    "\n",
    "# 作者：AccSrd\n",
    "# 链接：https://leetcode.cn/problems/factor-combinations/solutions/1210862/python3-zhao-shang-xia-jie-di-gui-by-acc-hpmr/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "        ret = []\n",
    "        def factorize(n, ub, prefix):\n",
    "            sqrt = int(math.sqrt(n))\n",
    "            for i in range(ub, sqrt + 1):\n",
    "                if n % i == 0:\n",
    "                    prefix.append(i)\n",
    "                    factorize(n // i, i, prefix)\n",
    "                    prefix.pop()\n",
    "            ret.append(prefix + [n])\n",
    "\n",
    "        factorize(n, 2, [])\n",
    "        return [l for l in ret if len(l) > 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "        if n == 1: return []\n",
    "        result = []\n",
    "        solution = []\n",
    "        def traverse(x: int, y: int, aim: int):\n",
    "            if aim == 1:\n",
    "                result.append(solution[:])\n",
    "                return\n",
    "            for i in range(x, y+1):\n",
    "                remain = aim % i\n",
    "                if remain == 0:\n",
    "                    solution.append(i)\n",
    "                    traverse(i, aim//i, aim//i)\n",
    "                    solution.pop()\n",
    "                            \n",
    "        traverse(2, int(math.sqrt(n)), n)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "# \tdef getFactors(self, n: int) -> List[List[int]]:\n",
    "\t\t\n",
    "# \t\tdef dfs(start, path, c):\n",
    "# \t\t\tif c < 1:\n",
    "# \t\t\t\treturn\n",
    "# \t\t\tif c == 1:\n",
    "# \t\t\t\tif path:\n",
    "# \t\t\t\t\tres.append(path.copy())\n",
    "# \t\t\t\treturn\n",
    "# \t\t\tfor i in range(start, n):\n",
    "# \t\t\t\tdfs(i, path + [i], c/i)\n",
    "\t\t\t\t\n",
    "# \t\tres = []\n",
    "# \t\tdfs(2, [], n)\n",
    "# \t\treturn res\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\tdef getFactors(self, n: int) -> List[List[int]]:\n",
    "\t\t\n",
    "\t\tdef dfs(start, path, c):\n",
    "\t\t\tif c == 1:\n",
    "\t\t\t\tif path:\n",
    "\t\t\t\t\tres.append(path.copy())\n",
    "\t\t\t\treturn\n",
    "\t\t\tfor i in range(start, n):\n",
    "\t\t\t\tif c % i != 0:\n",
    "\t\t\t\t\tcontinue\n",
    "\t\t\t\tdfs(i, path + [i], c/i)\n",
    "\t\t\t\t\n",
    "\t\tres = []\n",
    "\t\tdfs(2, [], n)\n",
    "\t\treturn res\n",
    "# class Solution:\n",
    "# \tdef getFactors(self, n: int) -> List[List[int]]:\n",
    "# \t\tif n == 1:\n",
    "# \t\t\treturn []\n",
    "# \t\tdef backtrace(start, remain):\n",
    "# \t\t\tfor i in range(start, int(remain**0.5)+1):\n",
    "# \t\t\t\tif remain % i != 0:\n",
    "# \t\t\t\t\tcontinue\n",
    "# \t\t\t\tpath.append(i)\n",
    "# \t\t\t\tres.append(path[:]+[remain // i])\n",
    "# \t\t\t\tbacktrace(i, remain // i)\n",
    "# \t\t\t\tpath.pop()\n",
    "\t\t\t\t\n",
    "# \t\tpath = []\n",
    "# \t\tres = []\n",
    "# \t\tbacktrace(2, n)\n",
    "# \t\treturn res\n",
    "\t\n",
    "\n",
    "# 作者：AccSrd\n",
    "# 链接：https://leetcode.cn/problems/factor-combinations/solutions/1210862/python3-zhao-shang-xia-jie-di-gui-by-acc-hpmr/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n",
    "class Solution:\n",
    "\tdef getFactors(self, n):\n",
    "\t\t\n",
    "\t\tdef DFS(num, start, path):\n",
    "\t\t\tsize = len(path)\n",
    "\t\t\tif num == 1:\n",
    "\t\t\t\tif size > 1:\n",
    "\t\t\t\t\tres.append(path[:])\n",
    "\t\t\telse:\n",
    "\t\t\t\tsqrt = int(num ** 0.5)\n",
    "\t\t\t\tfor i in range(start, sqrt + 1):\n",
    "\t\t\t\t\tif num % i == 0:\n",
    "\t\t\t\t\t\tpath.append(i)\n",
    "\t\t\t\t\t\tDFS(num // i, i, path)\n",
    "\t\t\t\t\t\tpath.pop()\n",
    "\t\t\t\tpath.append(num)\n",
    "\t\t\t\tDFS(1, num, path)\n",
    "\t\t\t\tpath.pop()\n",
    "\t\t\t\t\n",
    "\t\tres = []\n",
    "\t\tpath = []\n",
    "\t\tDFS(n, 2, path)\n",
    "\t\treturn res\n",
    "\t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getFactors(self, n: int) -> List[List[int]]:\n",
    "\n",
    "        m = {1: [], 2: [[2]]}\n",
    "        def factorize(n, lower_bound):\n",
    "            ret = []\n",
    "            upper_bound = math.ceil(math.sqrt(n))\n",
    "            for i in range(lower_bound, upper_bound + 1):\n",
    "                if i * i > n:\n",
    "                    break\n",
    "                if (n // i) * i == n:\n",
    "                    ret.extend([[i] + suffix for suffix in factorize(n // i, i)])\n",
    "            ret.append([n])\n",
    "            m[n] = ret\n",
    "            return ret\n",
    "        return [l for l in factorize(n, 2) if len(l) > 1]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
